package huawei.study;

import java.util.Scanner;

public class HuaWei16Test {


        public static void main(String[] args){
            // 输入数据
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            Goods[] goods = new Goods[m+1];
            for(int i=1; i<=m; i++){
                int v = in.nextInt();
                int p = in.nextInt();
                int q = in.nextInt();
                goods[i] = new Goods(v,p,q);
                // 如果商品是附件
                if(q > 0){
                    if(goods[q].addID1 == 0) goods[q].addID1 = i;
                    else goods[q].addID2 = i;
                }
            }

            // 处理网格
            int[][] dp = new int[m+1][n+1];
            for(int i=1; i<=m; i++){ // 第 i 个商品
                int v1 = 0, v2 = 0, v3 = 0, v4 = 0;
                int w1 = 0, w2 = 0, w3 = 0, w4 = 0;

                // 1. 主件
                v1 = goods[i].v;
                w1 = v1*goods[i].p;

                // 2. 主件 + 附件1
                if(goods[i].addID1 != 0){
                    v2 = v1 + goods[goods[i].addID1].v;
                    w2 = w1 + goods[goods[i].addID1].v*goods[goods[i].addID1].p;
                }

                // 3. 主件 + 附件2
                if(goods[i].addID2 != 0){
                    v3 = v1 + goods[goods[i].addID2].v;
                    w3 = w1 + goods[goods[i].addID2].v*goods[goods[i].addID2].p;
                }

                // 4. 主件 + 附件1 + 附件2
                if(goods[i].addID1 != 0 && goods[i].addID2 !=0){
                    v4 = v2 + v3 - v1;
                    w4 = w2 + w3 - w1;
                }

                for(int j=1; j<=n; j++){
                    if(goods[i].q > 0) {
                        dp[i][j] = dp[i-1][j]; // 附件行数据 会跟它的 主件行数据 一模一样
                        continue; // 跳过附件
                    }
                    // 对于主件行数据而言，它需要考虑四种情况里，自己选择哪种能够利益最大化
                    dp[i][j] = dp[i-1][j];
                    if(v1 <= j) dp[i][j] = Math.max(dp[i][j], w1+dp[i-1][j-v1]);
                    if(v2 <= j && v2 != 0) dp[i][j] = Math.max(dp[i][j], w2+dp[i-1][j-v2]);
                    if(v3 <= j && v3 != 0) dp[i][j] = Math.max(dp[i][j], w3+dp[i-1][j-v3]);
                    if(v4 <= j && v4 != 0) dp[i][j] = Math.max(dp[i][j], w4+dp[i-1][j-v4]);
                }
            }

            // 输出数据
            System.out.println(dp[m][n]);
        }

    // 商品类
}
class Goods{
    int v;
    int p;
    int q;

    int addID1 = 0; // 附件1的ID
    int addID2 = 0; // 附件2的ID

    public Goods(int v, int p, int q){
        this.v = v;
        this.p = p;
        this.q = q;
    }
}
